package com.ting.test.algorithms.排序算法.快速排序;

/**
 * 给定一个数组，并给定一个目标数X，要求:
 * 1. 小于等于目标数X的在目标数左边
 * 2. 大于目标数X的在目标数右边
 * <p>
 * 思路
 * 这是一个经典的荷兰国旗问题
 * 假设有左边界L和当期数Index，考虑两种情况
 * 1.当当前数小于等于目标数时，将左边界下一个数和当前数进行交换，同时左边界右移
 * 2.当当前数大于目标数时，左边界不动，当前数右移
 * 时间复杂度为O(n)
 */
public class 荷兰国旗问题_分2段 {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 41, 9, 2, 5, 3, 8, 6, 2};
        int[] result = helan(arr, 7);
        for (int num : result) {
            System.out.print(num + ",");
        }

    }

    /**
     * index表示当前数，
     * 当当前数小于等于目标数时，将
     *
     * @param arr
     * @param
     * @return
     */
    private static int[] helan(int[] arr, int X) {
        int L = -1;//左边界默认从下标-1位置开始
        int index = 0;
        while (index < arr.length) {
            if (arr[index] <= X) {
                swap(arr, ++L, index);
            }
            index++;

        }
        return arr;
    }

    private static void swap(int[] arr, int tar1, int tar2) {
        int temp = arr[tar1];
        arr[tar1] = arr[tar2];
        arr[tar2] = temp;
    }
}
